large_numbersfandomcom-20200214-history
Arrow notation
:For other arrow notations, see down-arrow notation and chained arrow notation. Arrow notation or up-arrow notation is a widely used notation for the hyper operators, devised by Donald Knuth in 1976 to represent large numbers.Arrow Notation from Wolfram Mathworld It is defined by the following rules: \begin{eqnarray} a \uparrow^1 b &=& a^b \\ a \uparrow^n 1 &=& a \\ a \uparrow^{n + 1} (b + 1) &=& a \uparrow^n (a \uparrow^{n + 1} b) \\ \end{eqnarray} \(a \uparrow^{n} b\) is a shorthand for \(a \uparrow\uparrow\cdots\uparrow\uparrow b\) with n'' arrows (where ''n is a positive integer). So, for example, \(a \uparrow^2 b = a \uparrow\uparrow b\). Arrow notation operators are right-associative; \(a \uparrow b \uparrow c\) always means \(a \uparrow (b \uparrow c)\). Specifically, \(a \uparrow b\) is exponentiation, \(a \uparrow\uparrow b\) is tetration, \(a \uparrow\uparrow\uparrow b\) is pentation, and so forth. In ASCII, these are written a^b, a^^b, a^^^b, ... The function \(f(n) = n \uparrow^n n\) is a fast-growing function that eventually dominates all primitive recursive functions, and can be approximated using the fast-growing hierarchy as \(f_\omega(n)\). Arrow notation has been generalized to other notations. A few notable ones are chained arrow notation, BEAF, and BAN. It has also been compared exactly with Notation Array Notation using the function (a{2, number of arrows}b). Nathan Ho and Wojowu showed that arrow notation terminates — that is, \(a \uparrow^n b\) exists for all \(a,b,n\).http://snappizz.com/termination Examples *\(2 \uparrow 3 = 2^3 = 8\) *\(5 \uparrow 6 = 5^6 = 15,625\) *\(10 \uparrow 100 = 10^{100} =\) googol *\(3 \uparrow\uparrow 4 = 3 \uparrow 3 \uparrow 3 \uparrow 3 = 3 \uparrow 3 \uparrow 27 = 3^{7,625,597,484,987}\) *\(5 \uparrow\uparrow 3 = 5 \uparrow 5 \uparrow 5 = 5^{5^5}\) *\(2 \uparrow\uparrow\uparrow 2 = 2 \uparrow\uparrow 2 = 2 \uparrow 2 = 2^2 = 4\) *\(2 \uparrow\uparrow\uparrow\uparrow 2 = 2 \uparrow\uparrow\uparrow 2 = 2 \uparrow\uparrow 2 = 2 \uparrow 2 = 2^2 = 4\) *\(3 \uparrow\uparrow\uparrow 2 = 3 \uparrow\uparrow 3 = 3 \uparrow 3 \uparrow 3 = 3^{3^3} = 3^{27} = 7,625,597,484,987\) *\(2 \uparrow\uparrow\uparrow 3 = 2 \uparrow\uparrow 2 \uparrow\uparrow 2 = 2 \uparrow\uparrow 4 = 2 \uparrow 2 \uparrow 2 \uparrow 2 = 2 \uparrow 2 \uparrow 4 = 2 \uparrow 16 = 65,536\) *\(3 \uparrow\uparrow\uparrow 3 = 3 \uparrow\uparrow 3 \uparrow\uparrow 3 = 3 \uparrow\uparrow 7,625,597,484,987 =\) Tritri See below nice examples of \(2 \uparrow^{n} 3\) series with colors for \(n = 1,2,3,4,5\): Turing machine code Input form: to represent \(a \uparrow^{c} b\), place a 1's, then c+2 ^'s, then b 1's. For example, 111^^^^^111 computes tritri. Turing machine code 0 * * r 0 0 _ _ l 1 1 1 _ l 2 2 ^ _ l 3 2 1 1 l 4 3 ^ _ l 3 3 1 _ l 2 4 1 1 l 4 4 ^ 1 l 4' 4 _ 1 l halt 4' ^ ^ l 5 4' 1 1 r 0 5 ^ ^ l 5 5 1 1 r 6 6 ^ x r 7 6 1 y r 9 6 | ^ l 12 7 * * r 7 7 _ | r 8 7 | | r 8 8 * * r 8 8 _ ^ l 11 9 * * r 9 9 | | r 10 10 * * r 10 10 _ 1 l 11 11 * * l 11 11 x ^ r 6 11 y 1 r 6 12 * * l 12 12 ^ ^ l 12' 12' ^ ^ l 12' 12' * * l 13 12' 1 x r 14 13 * * l 13 13 ^ ^ r 20 13 _ _ r 20 13 1 x r 14 14 * * r 14 14 ^ ^ r 15 15 ^ ^ r 15 15 x x r 16 15 1 x l 12 16 x x r 16 16 1 x l 12 16 ^ x r 17 17 ^ ^ r 17 17 1 ^ r 18 18 ^ 1 r 17 18 1 1 r 18 18 _ 1 l 19 19 * * l 19 19 x x l 12 20 x 1 r 20 20 ^ ^ r 21 21 ^ ^ r 21 21 x x r 22 22 x x r 22 22 1 _ r 23 22 ^ ^ l 30 23 1 _ r 23 23 ^ ^ l 24 24 _ ^ r 25 25 ^ ^ r 25 25 1 1 l 26 26 ^ 1 r 27 27 1 1 r 27 27 _ _ l 28 28 1 _ l 29 29 * * l 29 29 _ ^ r 25 29 x 1 l 30 30 x 1 l 30 30 ^ ^ r 31 31 * * r 31 31 _ _ l 32 32 1 _ l 1 See also *Down-arrow notation *Chained arrow notation *Ackermann number, a special case. *Bentley's Number *Hyper operator *Knuth Arrow Theorem Sources nl:Knuth's pijlomhoognotatie ja:矢印表記 zh:上箭號表示法